import lombok.Data;

/**
 * @author lzhphantom
 * @description
 * @date 创建于 19:09 2020/8/10
 * @modified
 */
public class BinarySearchTree {
    private BinarySearchNode root;

    public void add(int val) {
        if (this.root == null) {
            this.root = new BinarySearchNode(val);
            return;
        }
        this.root.add(val);
    }

    public BinarySearchNode findMinValue() {
        return this.root == null ? null : this.root.findMinValue();
    }

    public BinarySearchNode findMaxValue() {
        return this.root == null ? null : this.root.findMaxValue();
    }

    public BinarySearchNode find(int val) {
        return this.root == null ? null : this.root.find(val);
    }

    public BinarySearchNode findParent(int val) {
        return this.root == null || this.root.getVal() == val ? null : this.root.findParent(val);
    }

    public void delete(int val) {
        if (this.root == null) {
            return;
        }
        BinarySearchNode node = this.root.find(val);
        if (node == null) {
            return;
        }
        BinarySearchNode parent = this.root.findParent(val);
        if (parent == null && node.getLeft() == null && node.getRight() == null) {
            // 第一种情况，删除的是根节点，且根节点没有儿子
            this.root = null;
        } else if (node.getLeft() == null && node.getRight() == null && parent != null) {
            // 第二种情况，删除的节点有父亲节点，但没有子树
            if (parent.getLeft() != null && val == parent.getLeft().getVal()) {
                parent.setLeft(null);
            } else {
                parent.setRight(null);
            }
        } else if (node.getLeft() != null && node.getRight() != null) {
            //第三种情况，删除的节点下有两个子树，因为右子树的值都比左子树大，
            // 那么用右子树中的最小元素来替换删除的节点。
            // 右子树的最小元素，只要一直往右子树的左边一直找一直找就可以找到，替换后二叉查找树的性质又满足了。
            BinarySearchNode minNode = node.getRight();
            while (minNode.getLeft() != null) {
                minNode = minNode.getLeft();
            }
            this.delete(minNode.getVal());
            node.setVal(minNode.getVal());
            node.setTimes(minNode.getTimes());
        } else {
            // 第四种情况，只有一个子树，那么该子树直接替换被删除的节点即可
            if (parent == null) {
                if (node.getLeft() != null) {
                    this.root = node.getLeft();
                } else {
                    this.root = node.getRight();
                }
                return;
            }

            if (node.getLeft() != null) {
                if (parent.getLeft() != null && val == parent.getLeft().getVal()) {
                    parent.setLeft(node.getLeft());
                } else {
                    parent.setRight(node.getLeft());
                }
            } else {
                if (parent.getLeft() != null && val == parent.getLeft().getVal()) {
                    parent.setLeft(node.getRight());
                } else {
                    parent.setRight(node.getRight());
                }
            }
        }
    }

    public void midOrder() {
        if (this.root != null) {
            this.root.midOrder();
        }
    }

    public static void main(String[] args) {
        int[] arr = {3, 6, 8, 20, 9, 2, 6, 8, 9, 3, 5, 40, 7, 9, 13, 6, 8};
        BinarySearchTree tree = new BinarySearchTree();
        for (int i : arr) {
            tree.add(i);
        }
        System.out.println("min:" + tree.findMinValue());
        System.out.println("max:" + tree.findMaxValue());
        tree.midOrder();
    }
}

@Data
class BinarySearchNode {
    private int val;
    private int times;
    private BinarySearchNode left;
    private BinarySearchNode right;

    public BinarySearchNode(int val) {
        this.val = val;
        this.times = 1;
    }

    public void add(int val) {
        if (val < this.val) {
            if (this.left == null) {
                this.left = new BinarySearchNode(val);
            } else {
                this.left.add(val);
            }
        } else if (val > this.val) {
            if (this.right == null) {
                this.right = new BinarySearchNode(val);
            } else {
                this.right.add(val);
            }
        } else {
            this.times++;
        }
    }

    public BinarySearchNode findMinValue() {
        if (this.left == null) {
            return this;
        }
        return this.left.findMinValue();
    }

    public BinarySearchNode findMaxValue() {
        if (this.right == null) {
            return this;
        }
        return this.right.findMaxValue();
    }

    public BinarySearchNode find(int val) {
        if (val == this.val) {
            return this;
        } else if (val < this.val) {
            return this.left == null ? null : this.left.find(val);
        } else {
            return this.right == null ? null : this.right.find(val);
        }
    }

    public BinarySearchNode findParent(int val) {
        if (val < this.val) {
            BinarySearchNode leftTree = this.left;
            return leftTree == null ? null : leftTree.val == val ? this : leftTree.findParent(val);
        } else {
            BinarySearchNode rightTree = this.right;
            return rightTree == null ? null : rightTree.val == val ? this : rightTree.findParent(val);
        }
    }

    public void midOrder() {
        if (this.getLeft() != null) {
            this.getLeft().midOrder();
        }

        for (int i = 0; i < this.times; i++) {
            System.out.printf("\t%d", this.val);
        }
        if (this.getRight() != null) {
            this.getRight().midOrder();
        }
    }
}
